#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include"tree.h"


static node *__create(const void *data, int size);
static node **__find(const node **root, const void *data, cmp_t cmp);
static node * __get_max_tree(const node *n);
static node * __get_min_tree(const node *n);
static int count_node(node * root);
static void turn_left(node **n);
static void turn_right(node **n);

int root_init(head **tree, const int size){
	*tree = malloc(sizeof(head));
	if(NULL == *tree)
		return -1;
	(*tree)->root = NULL;
	(*tree)->size = size;
	
	return 0;
}
static node *__create(const void *data, int size){
	node * n = malloc(sizeof(node) + size);
	if(NULL == n)
		return NULL;
	memcpy(n->data, data, size);// 刚才想啥呢
	n->left = NULL;
	n->right = NULL;
	return n;
}

int __insert(node **root, node *key,cmp_t cmp){
	int res;
	if(NULL == *root){
		*root = key;
		return 0;
	}
	res = cmp((*root)->data, key->data);// 参数传进来的是点， 比较的的data 第一次错了
	if(res > 0){
		__insert(&((*root)->left), key, cmp);
	}else{
		__insert(&((*root)->right), key, cmp);
	}
	return 0;
}

int tree_insert(head *tree, const void *data, cmp_t cmp){
	node *n = __create(data, tree->size);
	printf("插入%c ", *(char *)data);
	if(NULL == n)
		return -1;
	__insert(&(tree->root), n,cmp);
	return 0;
}

static node **__find(const node **root, const void *data, cmp_t cmp){
	int res;
	if(NULL == *root)
		return NULL;
	res = cmp((*root)->data, data);
	if(res == 0){
		return (node **)root; 
	}else if(res > 0){
		return __find((const node **)&(*root)->left, data, cmp);
	}else{
		return __find((const node **)&(*root)->right, data, cmp);
	}

} 

static node * __get_max_tree(const node *n){
	if(n == NULL)
		return NULL;
	if(n->right == NULL){
		return (node *)n;
	}else{
		return __get_max_tree(n->right);
	}
}

static node * __get_min_tree(const node *n){
	if(n == NULL)
		return NULL;
	if(n->left == NULL){
		return(node *)n;
	}else{
		return __get_min_tree(n->left);
	}
}

/*
int tree_delete(head *tree, const void *data, cmp_t cmp){
	node **n = __find((const node **)&(tree->root), data, cmp);
	node *left = NULL;
	node *right = NULL;
	node *t = NULL;

	if(NULL == n)
		return -1;
	left = (*n)->left;
	right = (*n)->right;
	(*n)->left = (*n)->right = NULL; 
	free(*n);
	(*n) = left;
	if(NULL !=right){
		t = __get_max_tree(left);
		t->right = right;
	}
	return 0;
}
*/
int tree_delete(head *tree, const void *data, cmp_t cmp){
    node **n = __find((const node **)&(tree->root), data, cmp);
    node *left = NULL;
    node *right = NULL;
    node *t = NULL;

    if(NULL == n)
        return -1;

    left = (*n)->left;   // 保存左子树
    right = (*n)->right; // 保存右子树
    free(*n);            // 释放当前节点

    // 处理子树连接，避免空指针访问
    if (left == NULL) {
        // 左子树为空，直接用右子树替代当前节点位置
        *n = right;
    } else {
        // 左子树非空，先连接左子树
        *n = left;
        // 若右子树非空，将其接在左子树的最大节点右侧
        if (right != NULL) {
            t = __get_max_tree(left); // 左子树最大节点（最右侧节点）
            t->right = right;
        }
    }

    return 0;
}

void *tree_find(const head *tree, const void *key, cmp_t cmp){
	node **n = __find((const node **)&(tree->root), key, cmp);
	if(NULL == n){
		return NULL;
	}
	return (*n)->data;	
}

static void __traval(const node *n, pri_t pri){
	if(NULL == n)
		return;
	__traval(n->left, pri);
	pri(n->data);
	__traval(n->right, pri);
}

void tree_travel(const head *tree, pri_t pri){
	__traval((const node*)tree->root, pri);
}

void __destroy(node **root){
	if(NULL == *root)
		return;
	__destroy(&(*root)->left);
	__destroy(&(*root)->right);
	(*root)->left = (*root)->right = NULL;	
	free(*root);
	*root = NULL;
}
void tree_destroy(head **tree){
	__destroy(&(*tree)->root);
	(*tree)->root = NULL;
	free(*tree);
}

static int count_node(node * root){
	if(NULL == root){
		return 0;
	}else{
		return count_node(root->left) + count_node(root->right) + 1;
	}

}
/*
static void turn_left(node **n){
	node *cur = *n; //根节点 
	node *r = (*n)->right;
	cur->right = NULL; // 不能省！！！
	node *t = r->left;

	*n = r; // 用二级指针的原因  要修改
	r->left = cur;
	__get_max_tree(cur->left)->right = t;
}

static void turn_right(node **n){
	node *cur = *n; //根节点 
	node *l = (*n)->left;
	cur->left = NULL; // 不能省！！！
	node *t = l->right;
	
	l->right = cur;
	*n = l; // 用二级指针的原因  要修改
	__get_min_tree(cur->right)->left = t;
}

*/
static void turn_left(node **root)
{
    node *r, *cur;

    cur = *root;
    if (cur == NULL || cur->right == NULL) {
        return; // 空指针防护：当前节点或右子树为空时，直接返回
    }
    r = cur->right;

    *root = r;       // 右孩子成为新根
    cur->right = NULL; // 断开原连接
    node *min_r = __get_min_tree(r);
    if (min_r != NULL) {
        min_r->left = cur; // 原根节点接在新根的最小节点左子树
    } else {
        r->left = cur; // 若新根无左子树，直接连接原根节点
    }
}

static void turn_right(node **root)
{
    node *l, *cur;

    cur = *root;
    if (cur == NULL || cur->left == NULL) {
        return; // 空指针防护：当前节点或左子树为空时，直接返回
    }
    l = cur->left;

    *root = l;       // 左孩子成为新根
    cur->left = NULL; // 断开原连接
    node *max_l = __get_max_tree(l);
    if (max_l != NULL) {
        max_l->right = cur; // 原根节点接在新根的最大节点右子树
    } else {
        l->right = cur; // 若新根无右子树，直接连接原根节点
    }
}

static void __balance(node **root){
    if(NULL == *root)
        return;

    int res;
    do {
        res = count_node((*root)->left) - count_node((*root)->right);
        if(res >= 2){
            turn_right(root);
        } else if(res <= -2){
            turn_left(root);
        } else {
            break; // 平衡时退出循环
        }
    } while(1);

    __balance(&(*root)->left);  // 递归平衡左子树
    __balance(&(*root)->right); // 递归平衡右子树
}


void tree_balance(head *tree)
{
	__balance(&tree->root);
}



